백준 11505번

오늘 풀어본 문제는 백준의 11505번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

어떤 $N$ 개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 $1,\ 2,\ 3,\ 4,\ 5$ 라는 수가 있고, $3$ 번째 수를 $6$ 으로 바꾸고 $2$ 번째부터 $5$ 번째까지 곱을 구하라고 한다면 $240$ 을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 $2$ 로 바꾸고 $3$ 번째부터 $5$ 번째까지 곱을 구하라고 한다면 $48$ 이 될 것이다.

입력

첫째 줄에 수의 개수 $N$ $(1 \le N \le 1,000,000)$ 과 $M$ $(1 \le M \le 10,000)$, $K$ $(1 \le K \le 10,000)$ 가 주어진다. $M$ 은 수의 변경이 일어나는 횟수이고, $K$ 는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 $N+1$ 번째 줄까지 $N$ 개의 수가 주어진다. 그리고 $N+2$ 번째 줄부터 $N+M+K+1$ 번째 줄까지 세 개의 정수 $a,b,c$ 가 주어지는데, $a$ 가 $1$ 인 경우 $b$ 번째 수를 $c$ 로 바꾸고 $a$ 가 $2$ 인 경우에는 $b$ 부터 $c$ 까지의 곱을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 $0$ 보다 크거나 같고, $1,000,000$ 보다 작거나 같은 정수이다.

출력

첫째 줄부터 $K$ 줄에 걸쳐 구한 구간의 곱을 $1,000,000,007$ 로 나눈 나머지를 출력한다.

풀이과정

1번째 시도

전형적인 세그먼트 트리를 활용하는 문제라는 것을 알 수 있었다. 다른 점이 있다면, 보통 덧셈 연산을 이용하는 경우가 많았는데 곱셈을 대신 이용해야 한다는 점이었다.

코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.

segment_tree.hpp

#ifndef __SEGMENT_TREE_HPP__
#define __SEGMENT_TREE_HPP__

#include <vector>

template <typename T>
class SegmentTree {
private:
    std::vector<T> tree;
    std::vector<T> arr;
    size_t n;

    void build(size_t idx, size_t left, size_t right) {
        if (left == right) {
            tree[idx] = arr[left];
            return;
        }

        size_t mid = (left + right) / 2;

        build(2 * idx, left, mid);
        build(2 * idx + 1, mid + 1, right);

        const T& leftValue = tree[2 * idx];
        const T& rightValue = tree[2 * idx + 1];

        tree[idx] = leftValue * rightValue;
    }

    void update(size_t index, const T& value, size_t node, size_t currentLeft, size_t currentRight) {
        if (currentLeft <= index && index <= currentRight) {
            if (currentLeft == currentRight) {
                tree[node] = value;
            }
            else {
                size_t mid = (currentLeft + currentRight) / 2;

                update(index, value, 2 * node, currentLeft, mid);
                update(index, value, 2 * node + 1, mid + 1, currentRight);

                tree[node] = tree[2 * node] * tree[2 * node + 1];
            }
        }
    }

    const T query(size_t i, size_t j, size_t node, size_t currentLeft, size_t currentRight) {
        if (j < currentLeft || currentRight < i) {
            return static_cast<T>(1);
        }
        else if (i <= currentLeft && currentRight <= j) {
            return tree[node];
        }
        else {
            size_t mid = (currentLeft + currentRight) / 2;
            const T leftValue = query(i, j, 2 * node, currentLeft, mid);
            const T rightValue = query(i, j, 2 * node + 1, mid + 1, currentRight);

            return leftValue * rightValue;
        }
    }

public:
    SegmentTree(const std::vector<T>& a) : arr(a), n(a.size()) {
        tree.resize(4 * n + 1);
        build(1, 0, n - 1);
    }

    void update(size_t index, const T& value) {
        update(index, value, 1, 0, n - 1);
        arr[index] = value;
    }

    const T query(size_t i, size_t j) {
        return query(i, j, 1, 0, n - 1);
    }
};

#endif // !__SEGMENT_TREE_HPP__

main.hpp

#include <bits/extc++.h>
#include "segment_tree.hpp"

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

struct MyMonoid {
    ull num;

    MyMonoid(ull num=1) : num(num % 1000000007ULL) {}

    MyMonoid operator*(const MyMonoid& other) const {
        return MyMonoid(num * other.num);
    }
};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ull N, M, K;
    cin >> N >> M >> K;

    vector<MyMonoid> arr(N);
    for (ull i=0; i<N; i++) {
        ull temp;
        cin >> temp;

        arr[i] = MyMonoid(temp);
    }

    SegmentTree<MyMonoid> segtree(arr);

    for (ull i=0; i<M+K; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        if (a == 1) {
            segtree.update(b-1, MyMonoid(c));
        }
        else {
            cout << segtree.query(b-1, c-1).num << '\n';
        }
    }
    
    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

예전 글들과 코드를 자세히 봤다면 알겠지만, 기존의 SegmentTree 자료 구조에서 곱셈 연산을 기본으로 사용하도록 설정한 것을 볼 수 있을 것이다. 이렇게 한 이유는 세그먼트 트리를 다양한 ‘모노이드’ 형태의 자료구조에 대해 사용할 수 있는데, 모노이드의 연산에는 commutative property 가 존재하지 않기 때문이다. 최근에 읽었던 현대대수학 전공책에서 그러한 연산은 덧셈기호 대신 곱셈기호를 사용하는 것이 관례라고 적혀있어, 그것을 따르기로 한 것이다.

그래서 앞으로 세그먼트 트리를 사용하는 거의 모든 (혹은 모든) 문제에서 SegmentTree 자료구조는 그대로 두고 그때그때 문제 상황에 맞는 모노이드 자료형을 만들어 세그먼트 트리에 사용할 계획이다. 모노이드가 무엇인지는 인터넷의 여러 글과 자료가 자세히 친절히 설명하고 있으니 여기서는 생략하도록 하겠다.

내가 만든 세그먼트 트리 자료구조는 내 레포지토리²에서 확인할 수 있다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11505
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/segment_tree.hpp

← Previous Post Next Post →